Java每日一题：876.链表的中间节点解析

本文将深入探讨LeetCode上的经典算法题——876. 链表的中间节点。我们将详细介绍题目的要求、解题思路以及具体的代码实现。

题目描述

给定一个非空单链表的头节点 head，返回链表的中间节点。如果链表中有两个中间节点，则返回第二个中间节点。

示例

示例 1:

输入: [1, 2, 3, 4, 5]
输出: 此列表中的结点 3

示例 2:

输入: [1, 2, 3, 4, 5, 6]
输出: 此列表中的结点 4

解题思路

为了找到链表的中间节点，我们可以使用快慢指针法。具体步骤如下：

• 初始化两个指针，slow 和 fast，均指向链表的头节点。


• 遍历链表时，slow 每次移动一步，而 fast 每次移动两步。


• 当 fast 到达链表末尾时，slow 所在的位置即为链表的中间节点。

对于偶数长度的链表，fast 最终会指向 null，此时 slow 即为所需的中间节点。对于奇数长度的链表，fast 的下一个节点为 null，此时 slow 也指向中间节点。

代码实现

public class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

ListNode 类定义

public class ListNode {
    int val;
    ListNode next;
    public ListNode() {}
    public ListNode(int val) { this.val = val; }
    public ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

测试代码

import org.junit.Test;

public class TestSolution {
    @Test
    public void testMiddleNode() {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next = new ListNode(6);
        ListNode result = new Solution().middleNode(head);
        System.out.println(result.val); // 输出 4
    }
}

复杂度分析

时间复杂度: O(n)，其中 n 是链表的长度，因为我们需要遍历整个链表一次。

空间复杂度: O(1)，因为我们只使用了常数级别的额外空间。